package org.test.analysis;

import org.junit.Test;

/**
 * 字符串匹配算法
 * @author game
 *
 */
public class Boyer_Moore {
	
	/**
	 * 外部调用这个函数就OK了
	 * @param s  子串
	 * @param t	  父串
	 * @return   匹配的父串第一个字符index,若为-1则无匹配
	 */
	public int matchIndex(char[] s,char[] t){
		
		//初始化table
		int[] betable = new int[255];
		int[] gstable = new int[s.length];
		badelement(s, betable);
		goodsuffix(s, gstable);
		
		int totalcom = 0;// 用来确定比较了多少次
		
		int k=0;//匹配了多少个
		int j = 0;
		for (int i = 0; i < t.length-s.length+1;) { //
			totalcom++;
			for ( j = 0; j < s.length; ) { //逐字匹配
				if(s[s.length-1-j]==t[i+s.length-1-j]){ //匹配了，转前一字符
					j++;
					k++;
				}else{ //不匹配，要滑动了,变i后,break
					if(k==0){
						i+=betable[t[i+s.length-1-j]];
					}else if(betable[t[i+s.length-1-j]]-k>gstable[k]){ //坏分子大
						i+=betable[t[i+s.length-1-j]]-k;
					}else{  //好后缀大
						i+=gstable[k];
					}
					break;
				}
			}
			if(j==s.length){ //完全匹配，返回index 
				System.out.println("共比较了"+totalcom+"次");
				return i;
			}
		}
		System.out.println("共比较了"+totalcom+"次");
		return -1;//无匹配
	}
	
	
	/**
	 * 填充坏分子表
	 * @param s  子串
	 * @param betable 要填充的坏分子table,长度为255
	 */
	public void badelement(char[] s ,int[] betable){
		for (int i = 0; i < betable.length; i++) {
			betable[i]=s.length;
		}
		for (int i = 0; i < s.length-1; i++) {
			betable[s[i]]=s.length-1-i;
			//最低为1
			if(betable[s[i]]<1){
				betable[s[i]]=1;
			}
		}
	}
	
	/**
	 * 填充好后缀表
	 * @param s 串
	 * @param gstable 好后缀表，数组的下标作为其后缀匹配的个数，最低为1,长度为s.length
	 */
	public void goodsuffix(char[] s,int gstable[]){
		for (int i = 0; i < s.length; i++) {
			gstable[i]=goodsuffixhelp(s, i);
		}
	}
	
	/**
	 * 找出 串s中n个后缀要滑动的距离
	 * @param s
	 * @param n
	 */
	public int goodsuffixhelp(char[] s,int n){
		if(n<1){
			return 1;
		}else if(n>=s.length){
			System.out.println("错误，n值太大了");
			return -1;
		}
		int sleng=s.length;
		int k = sleng-n;//s中指定后缀的第一字符index
		int i=0,j=0;
		for (j=k-1; j > 0-n;j--) { // 向左滑行,可以越到负数那
			
			for (i = 0; i < n;) {//逐字匹配
				if(j+i<0){ //越界了，配后面的字符
					i++;
				}else if(s[j+i]==s[k+i]){//匹配了,转下一个字符
					i++;
				}else{ //不能匹配
					break;
				}
			}
			if(i==n){//说明匹配了,返回要滑动的距离。
				return k-j;
			}
		}
		if(j==0-n){ //说明没有匹配的,直接返回长度
			return sleng;
		}
		return n;
	}
}
